/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        //1、如果右子树存在，那么下一个结点是其右子树的最左边结点
        if(pNode->right)
        {
            pNode=pNode->right;
            while(pNode->left)
                pNode=pNode->left;
            return pNode;
        }
        //2、如果右子树不存在，向上找
        while(pNode->next)
        {  //2.1如果其是父节点的左孩子，其父节点就是要找的
            if(pNode->next->left==pNode)
            {
                return pNode->next;
            }
            //2.1继续向上走
            pNode=pNode->next;
        }
        return NULL;
    }
};